package com.algorithm;

import java.util.Random;

/**
 * 当length = 10000时 单位毫秒
 * 算法1执行时间479834
 * 算法2执行时间137793
 * 算法3执行时间2
 * 算法4执行时间1
 * Created by houjinxin on 16/5/8.
 */
public class MaxSub {

    public static void main(String[] args) {
        int length = 1000;
        int[] a = new int[length];
        Random random = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(length);
        }

//        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        long begin1 = System.currentTimeMillis();
        int max1 = maxSub1(a);
        long end1 = System.currentTimeMillis();
        long begin2 = System.currentTimeMillis();
        int max2 = maxSub2(a);
        long end2 = System.currentTimeMillis();
        long begin3 = System.currentTimeMillis();
        int max3 = maxSub3(a);
        long end3 = System.currentTimeMillis();
        long begin4 = System.currentTimeMillis();
        int max4 = maxSub4(a);
        long end4 = System.currentTimeMillis();
        System.out.println("算法1执行时间"+ (end1 - begin1)+"最大子序列和是:"+max1);
        System.out.println("算法2执行时间"+ (end2 - begin2)+"最大子序列和是:"+max2);
        System.out.println("算法3执行时间"+ (end3 - begin3)+"最大子序列和是:"+max3);
        System.out.println("算法4执行时间"+ (end4 - begin4)+"最大子序列和是:"+max4);
    }

    /**
     * 枚举法取子列最大值, 这里从指定的元素位置开始,只按照从左往右的顺序取子列
     * <p>
     * l表示数列长度
     * i表示取子列左边位置
     * j表示右边的位置
     * k从左到右计算子列和
     * <p>
     * 算法的时间复杂度T(N) = O(N^3) 原因:三层嵌套循环,设数据规模为n,第一层执行次数为n,第二层执行次数为(n-0) + (n-1) + ... + (n - n + 1),
     * 第三层循环执行次数(n - (n-0)) + (n - (n-1)) +  ... + n
     * 总共执行的次数通过相乘得到 n * ((n-0) + (n-1) + ... + (n - n + 1)) * ((n - (n-0)) + (n - (n-1)) +  ... + n),
     * 可以推知这个式子最终可以转换为 c1n^3 + c2n^2 + c3n + c4 故时间复杂度为T(N) = O(N^3)
     *
     * @param a
     * @return
     */
    public static int maxSub1(int[] a) {
        int max = 0;
        int thisSum;
        int l = a.length;
        for (int i = 0; i < l; i++) {
            for (int j = i; j < l; j++) {
                thisSum = 0;
                for (int k = i; k <= j; k++) {
                    thisSum += a[k];
                }
                System.out.println("a[" + i + "]-a[" + j + "]的子列和thisSum:" + thisSum);
                if (thisSum > max) {
                    max = thisSum;
                }
            }
        }
        return max;
    }

    /**
     * 并不需要每次都计算子列全部元素的和,其实可以复用上个子列的和,并在此和基础上加上下一个元素即可
     * <p>
     * 算法的时间复杂度T(N) = O(N^2) 原因: 第一层执行次数n, 第二层执行次数(n-0) + (n-1) + ... + (n - n + 1)
     * 总共执行的次数通过相乘得到 n * ((n-0) + (n-1) + ... + (n - n + 1))\
     * 可以推知这个式子最终可以转换为 c1n^2 + c2n + c3 故时间复杂度为T(N) = O(N^2)
     *
     * @param a
     * @return
     */
    public static int maxSub2(int[] a) {
        int max = 0;
        int thisSum;
        int l = a.length;
        for (int i = 0; i < l; i++) {
            thisSum = 0;
            for (int j = i; j < l; j++) {
                thisSum += a[j];
                System.out.println("a[" + i + "]-a[" + j + "]的子列和thisSum:" + thisSum);
                if (thisSum > max) {
                    max = thisSum;
                }
            }
        }
        return max;
    }

    /**
     * 分治法(递归), 将序列分为前后两部分,最大子列和可能出现在:
     * 1.左半部分
     * 2.右半部分
     * 3.跨越输入数据的中部从而位于左右两部分之中
     * 前两种情况可用递归求解,第三种情况可以计算左半部分(包含最后一项)和右半部分(包含第一项)的最大和得到
     *
     * 算法的时间复杂度T(N)=O(NlogN) 原因:首先是递归求解左右部分的时间复杂度分别为T(N/2),故和为2T(N/2).
     * 处理第三部分时的时间复杂度为T(N) = O(N),故整体的时间复杂度可表示为T(N) = 2T(N/2) + CN, C为常数
     * T(N/2) = 2 T(N/4) + CN/2 ==> T(N) = 2( 2 T(N/4) + CN/2) + CN
     * 通过分析这是式子可知 每次递归处理的数据规模减半,递归处理推演到基准情形时待处理数据为1(未必为1,但和1的情况差不多),假设递归次数为k,可得
     * N/(2^k) = 1 ==> N = 2^k ==> k = logN
     *
     *  T(N) = 2( 2 T(N/4) + CN/2) + CN 当执行k次时 T(N) = 2^k * T(1) + kCN
     *  T(1) = O(1) ==> T(N) = 2^k * O(1) + CNlogN ==> T(N)=O(NlogN)
     *
     * @param a
     * @return
     */
    public static int maxSub3(int[] a) {
        return maxSumRec(a, 0, a.length - 1);
    }

    private static int maxSumRec(int[] a, int left, int right) {
        int center = (left + right) / 2;
        //递归基准情形
        if (left == right) {
            return a[left] > 0 ? a[left] : 0;
        }
        //分别计算左右最大子列和
        int maxLeftSum = maxSumRec(a, left, center);
        int maxRightSum = maxSumRec(a, center + 1, right);
        //计算第三种情况
        //计算左半部分(包含最后一项)最大和
        int maxLeftBorderSum = 0, leftBorderSum = 0;
        for (int i = left; i <= center; i++) {
            leftBorderSum += a[i];
            if (leftBorderSum > maxLeftBorderSum){
                maxLeftBorderSum = leftBorderSum;
            }
        }
        //计算右半部分(包含第一项)的最大和
        int maxRightBorderSum = 0, rightBorderSum = 0;
        for (int i = center + 1; i <= right; i++) {
            rightBorderSum += a[i];
            if (rightBorderSum > maxRightBorderSum){
                maxRightBorderSum = rightBorderSum;
            }
        }
        //跨越中部的最大子列和
        int maxBorderSum = maxLeftBorderSum + maxRightBorderSum;
        int max = maxLeftSum;
        if (maxRightSum > max){
            max = maxRightSum;
        }
        if (maxBorderSum > max){
            max = maxBorderSum;
        }
        return max;
    }

    /**
     * 在线处理:没输入一个数据就进行处理,在任何一个地方终止输入,算法都能正确给出当前解
     *
     * 最大和肯定是一个大于零的正数,若一个负数+正数 必然小于该正数,故这是为了计算最大子列和将之前为负的计算结果清零
     *
     * @param a
     * @return
     */
    public static int maxSub4(int[] a) {
        int thisSum = 0;
        int maxSum = 0;
        int l = a.length;
        for (int i = 0; i < l; i++) {
            thisSum += a[i];
            if (thisSum > maxSum){ //发现更大和则更新最大和
                maxSum = thisSum;
            } else if(thisSum < 0) { //若thisSum小于0, 则说明前几项的则说明最大和肯定在后面
                thisSum = 0; //不可使后面的子列和增加
            }
        }
        return maxSum;
    }

}
